Target devices such as field programmable gate arrays (FPGAs), structured application specific integrated circuits (ASICs), and ASICs are used to implement large systems that may include million of gates and megabits of embedded memory. The complexity of a large system often requires the use of electronic design automation (EDA) tools to create and optimize a design for the system onto physical target devices. Among the procedures performed by EDA tools in a computer aided design (CAD) compilation flow are design generation and integration, synthesis, placement, and routing of the system on the target device.
When addressing conventional timing closure, designers focus on the critical paths in a design. A critical path is a path from a register to another register, through combinational or routing elements, which fails or is close to failing a timing requirement. In an effort to close timing, a designer may examine the critical path and attempt to improve it by reducing an amount of combinational or routing delay along the path.
EDA tools may utilize register retiming algorithms in order to close timing. Register retiming is a synchronous circuit transformation that is used to improve the speed-performance of a synchronous circuit. Register retiming involves moving register across combinational or routing circuit elements in order to reduce the length of timing-critical paths. The combinational structure remains unchanged and the observable behavior of the circuit is identical to the original circuit. When performing register retiming, EDA tools need also address issues such as multiple timing constraints, asynchronous conditions, and architectural constraints.